package 简单算法;

import java.util.*;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-21
 * @Description: 给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。
 * 样例
 * 样例 1:
 * <p>
 * 输入: [1, 1, 1, 1, 2, 2, 2]
 * 输出: 1
 * 样例 2:
 * <p>
 * 输入: [1, 1, 1, 2, 2, 2, 2]
 * 输出: 2
 * 挑战
 * 要求时间复杂度为O(n)，空间复杂度为O(1)
 * <p>
 * 注意事项
 * 你可以假设数组非空，且数组中总是存在主元素。
 **/
public class 主元素 {
    public static void main(String[] args) {
        主元素 s = new 主元素();
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(1);
        nums.add(1);
        nums.add(1);
        nums.add(2);
        nums.add(2);
        nums.add(2);
        nums.add(3);
        nums.add(3);
        nums.add(3);
        nums.add(3);
        System.out.println(s.majorityNumber(nums));
    }

    public int majorityNumber(List<Integer> nums) {
        // write your code here
        int key = 0;
        Map<String, Integer> map = new HashMap<>();
        HashSet set = new HashSet(nums);
        for (int i = 0; i < nums.size(); i++) {
            map.put(nums.get(i) + "", (map.get(nums.get(i) + "") == null ? 0 : map.get(nums.get(i) + "")) + 1);
            if (map.get(nums.get(i) + "") > nums.size() / set.size()) {
                key = nums.get(i);
                break;
            }
        }
        return key;
    }

}
